Find the Maximum Sum Subarray (Kadane’s Algorithm)

function maxSubArray(nums) {
    int maxSoFar = nums[0], maxEndingHere = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
            

Find the Missing Number in an Array

function findMissingNumber(nums) {
    int n = nums.size();
    int total = (n + 1) * (n + 2) / 2; // Sum from 1 to n+1
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
    }
    return total - sum;
}
            

Find the Duplicate Number in an Array

function findDuplicate(nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    
    fast = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}
            

Rotate an Array

function rotate(nums, k) {
    int n = nums.size();
    k = k % n;  // In case k is larger than n
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}
            

Move All Zeros to the End of an Array

function moveZeroes(nums) {
    int lastNonZeroIndex = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            swap(nums[i], nums[lastNonZeroIndex]);
            lastNonZeroIndex++;
        }
    }
}
            

Find the Intersection of Two Arrays

function intersection(nums1, nums2) {
    unordered_set set(nums1.begin(), nums1.end());
    vector result;
    for (int num : nums2) {
        if (set.count(num)) {
            result.push_back(num);
            set.erase(num);  // Avoid duplicates
        }
    }
    return result;
}
            

Find the Majority Element in an Array (Boyer-Moore Voting Algorithm)

function majorityElement(nums) {
    int count = 0, candidate = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}
            

Merge Two Sorted Arrays

function merge(nums1, nums2) {
    int i = 0, j = 0;
    vector merged;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) merged.push_back(nums1[i++]);
        else merged.push_back(nums2[j++]);
    }
    while (i < nums1.size()) merged.push_back(nums1[i++]);
    while (j < nums2.size()) merged.push_back(nums2[j++]);
    return merged;
}
            

Find the Longest Subarray with Sum 0

function longestSubarray(nums) {
    unordered_map map;
    int sum = 0, maxLength = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        if (sum == 0) maxLength = i + 1;
        else if (map.count(sum)) maxLength = max(maxLength, i - map[sum]);
        else map[sum] = i;
    }
    return maxLength;
}
            

Check if a String is a Palindrome

function isPalindrome(s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}
            

Implement strstr (Substring Search)

function strStr(haystack, needle) {
    if (needle.empty()) return 0;
    for (int i = 0; i <= haystack.size() - needle.size(); i++) {
        if (haystack.substr(i, needle.size()) == needle) return i;
    }
    return -1;
}
            

Reverse an Array in Place

function reverseArray(nums) {
    int start = 0, end = nums.size() - 1;
    while (start < end) {
        swap(nums[start], nums[end]);
        start++;
        end--;
    }
}
            

Find the Longest Common Prefix of Strings

function longestCommonPrefix(strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
        }
    }
    return prefix;
}
            

Maximum Product Subarray

function maxProduct(nums) {
    int maxProduct = nums[0], minProduct = nums[0], result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) swap(maxProduct, minProduct);
        maxProduct = max(nums[i], maxProduct * nums[i]);
        minProduct = min(nums[i], minProduct * nums[i]);
        result = max(result, maxProduct);
    }
    return result;
}
            

Implement atoi (String to Integer Conversion)

function myAtoi(str) {
    int i = 0, sign = 1, result = 0;
    while (i < str.size() && str[i] == ' ') i++;
    if (i < str.size() && (str[i] == '+' || str[i] == '-')) {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }
    while (i < str.size() && isdigit(str[i])) {
        result = result * 10 + (str[i] - '0');
        i++;
    }
    return sign * result;
}
            

Rearrange an Array Such that arr[i] = i

function rearrange(nums) {
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] != i && nums[nums[i]] != nums[i]) {
            swap(nums[i], nums[nums[i]]);
        }
    }
}
            

Next Permutation

function nextPermutation(nums) {
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}
            

Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
    unordered_map map;
    int start = 0, maxLength = 0;
    for (int end = 0; end < s.size(); end++) {
        if (map.count(s[end])) start = max(start, map[s[end]] + 1);
        map[s[end]] = end;
        maxLength = max(maxLength, end - start + 1);
    }
    return maxLength;
}
            

Find the Shortest Path in a Binary Matrix

function shortestPathBinaryMatrix(grid) {
    if (grid[0][0] == 1 || grid[grid.size() - 1][grid[0].size() - 1] == 1) return -1;
    int n = grid.size();
    vector> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    queue> q;
    q.push({0, 0});
    grid[0][0] = 1;
    int steps = 1;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front(); q.pop();
            if (x == n - 1 && y == n - 1) return steps;
            for (auto dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    q.push({nx, ny});
                    grid[nx][ny] = 1;
                }
            }
        }
        steps++;
    }
    return -1;
}